From 70fa05a7bd123048b83351c9d9d7049740e57100 Mon Sep 17 00:00:00 2001 From: parkrrrr Date: Tue, 2 Dec 2003 23:59:36 +0000 Subject: [PATCH] Added 'simplify' filter --- Makefile | 3 +- README | 20 +++ defs.h | 1 + filter_vecs.c | 6 + reference/simplify_output.txt | 13 ++ route.c | 10 ++ smplrout.c | 251 ++++++++++++++++++++++++++++++++++ testo | 10 +- 8 files changed, 311 insertions(+), 3 deletions(-) create mode 100644 reference/simplify_output.txt create mode 100644 smplrout.c diff --git a/Makefile b/Makefile index c4a8b1203..d7ed7c67d 100644 --- a/Makefile +++ b/Makefile @@ -20,7 +20,7 @@ FMTS=magproto.o gpx.o geo.o mapsend.o mapsource.o \ xcsv.o gcdb.o tiger.o internal_styles.o easygps.o quovadis.o \ gpilots.o saroute.o navicache.o psitrex.o geoniche.o -FILTERS=position.o duplicate.o arcdist.o polygon.o +FILTERS=position.o duplicate.o arcdist.o polygon.o smplrout.o JEEPS=jeeps/gpsapp.o jeeps/gpscom.o \ jeeps/gpsmath.o jeeps/gpsmem.o \ @@ -128,6 +128,7 @@ quovadis.o: quovadis.c quovadis.h defs.h queue.h coldsync/palm.h \ coldsync/pdb.h route.o: route.c defs.h queue.h saroute.o: saroute.c defs.h queue.h +smplrout.o: smplrout.c defs.h grtcirc.h tiger.o: tiger.c defs.h queue.h csv_util.h tmpro.o: tmpro.c defs.h queue.h csv_util.h tpg.o: tpg.c defs.h queue.h jeeps/gpsmath.h jeeps/gps.h jeeps/gpsport.h \ diff --git a/README b/README index 896627f2e..62c713eff 100644 --- a/README +++ b/README @@ -578,6 +578,26 @@ DATA FILTERS gpsbabel -i geo -f 1.loc -x polygon,file=mycounty.txt \ -o mapsend -F 2.wpt + SIMPLIFY + + The Simplify filter is used to simplify routes and tracks for use + with formats that limit the number of points they can contain. + The filter takes one required parameter, which is the maximum + number of points a route may contain. It attempts to remove + points from each route until the number of points is at or below + the given maximum, while also attempting to preserve the shape of + the original route as much as possible. + + The quality of the results will vary depending on the density of + points in the original route and the length of the original route. + + For example, suppose you have a route from Street Atlas 2003 that + you wish to use with a Magellan GPS receiver that only supports up + to 50 points in a route: + + gpsbabel -r -i saroute -f RoadTrip.anr -x simplify,count=50 \ + -o magellan -F grocery.rte + COMMON USAGE Invocation was meant to be flexible. Unfortunately, that can diff --git a/defs.h b/defs.h index 1ddf18c08..0a32f8255 100644 --- a/defs.h +++ b/defs.h @@ -207,6 +207,7 @@ waypoint * find_waypt_by_name(const char *name); route_head *route_head_alloc(void); void route_add (waypoint *); void route_add_wpt(route_head *rte, waypoint *wpt); +void route_del_wpt(route_head *rte, waypoint *wpt); void route_add_head(route_head *rte); void route_disp_all(route_hdr, route_trl, waypt_cb); void route_free (route_head *); diff --git a/filter_vecs.c b/filter_vecs.c index c8b84afd3..3da4816f9 100644 --- a/filter_vecs.c +++ b/filter_vecs.c @@ -33,6 +33,7 @@ extern filter_vecs_t radius_vecs; extern filter_vecs_t duplicate_vecs; extern filter_vecs_t arcdist_vecs; extern filter_vecs_t polygon_vecs; +extern filter_vecs_t routesimple_vecs; static fl_vecs_t filter_vec_list[] = { @@ -61,6 +62,11 @@ fl_vecs_t filter_vec_list[] = { "polygon", "Include Only Points Inside Polygon", }, + { + &routesimple_vecs, + "simplify", + "Simplify routes", + }, { NULL, NULL, diff --git a/reference/simplify_output.txt b/reference/simplify_output.txt new file mode 100644 index 000000000..b10c3d3c4 --- /dev/null +++ b/reference/simplify_output.txt @@ -0,0 +1,13 @@ +30.70000 -92.40000 +30.20000 -92.30000 +29.40000 -92.20000 +28.40000 -91.40000 +27.80000 -91.10000 +26.60000 -90.30000 +24.40000 -88.40000 +23.60000 -87.20000 +23.00000 -85.60000 +22.30000 -84.40000 +30.28052 -91.68588 +30.29105 -91.62717 +30.31472 -91.64612 diff --git a/route.c b/route.c index 9eeff49a9..70c597bb9 100644 --- a/route.c +++ b/route.c @@ -69,6 +69,15 @@ route_add_wpt(route_head *rte, waypoint *wpt) rte_waypts++; /* total waypoints in all routes */ } +void +route_del_wpt( route_head *rte, waypoint *wpt) +{ + dequeue( &wpt->Q ); + waypt_free( wpt ); + rte->rte_waypt_ct--; + rte_waypts--; +} + void route_free(route_head *rte) { @@ -78,6 +87,7 @@ route_free(route_head *rte) if ( rte->rte_desc ) { xfree(rte->rte_desc); } + rte_waypts -= rte->rte_waypt_ct; waypt_flush(&rte->waypoint_list); xfree(rte); } diff --git a/smplrout.c b/smplrout.c new file mode 100644 index 000000000..90f188263 --- /dev/null +++ b/smplrout.c @@ -0,0 +1,251 @@ +/* + Route simplification filter + + Copyright (C) 2002 Robert Lipe, robertlipe@usa.net + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA + + */ +#include +#include "defs.h" +#include "grtcirc.h" + +#define MYNAME "Route simplification filter" + +static int count = 0; +static char *countopt = NULL; + +static +arglist_t routesimple_args[] = { + {"count", &countopt, "Maximum number of points in final route", + ARGTYPE_INT | ARGTYPE_REQUIRED}, + {0, 0, 0, 0} +}; + +struct xte_intermed; + +struct xte { + double distance; + int ordinal; + struct xte_intermed *intermed; +}; + +struct xte_intermed { + struct xte *xte_rec; + struct xte_intermed *next; + struct xte_intermed *prev; + const waypoint *wpt; +}; + +void +free_xte( struct xte *xte_rec ) +{ + xfree(xte_rec->intermed); +} + +#define HUGEVAL 9e9; + +static struct xte_intermed *tmpprev = NULL; +static int xte_count = 0; +static const route_head *cur_rte = NULL; +static struct xte *xte_recs = NULL; + +void +routesimple_waypt_pr( const waypoint *wpt ) +{ + if ( !cur_rte ) return; + xte_recs[xte_count].ordinal=xte_count; + xte_recs[xte_count].intermed = xmalloc( sizeof(struct xte_intermed)); + xte_recs[xte_count].intermed->wpt = wpt; + xte_recs[xte_count].intermed->xte_rec = xte_recs+xte_count; + xte_recs[xte_count].intermed->next = NULL; + xte_recs[xte_count].intermed->prev = tmpprev; + if ( tmpprev ) { + tmpprev->next = xte_recs[xte_count].intermed; + } + tmpprev = xte_recs[xte_count].intermed; + xte_count++; +} + +void +compute_xte( struct xte *xte_rec ) { + const waypoint *wpt3 = xte_rec->intermed->wpt; + const waypoint *wpt1 = NULL; + const waypoint *wpt2 = NULL; + /* if no previous, this is an endpoint and must be preserved. */ + if ( !xte_rec->intermed->prev ) { + xte_rec->distance = HUGEVAL; + return; + } + wpt1 = xte_rec->intermed->prev->wpt; + + /* if no next, this is an endpoint and must be preserved. */ + if ( !xte_rec->intermed->next ) { + xte_rec->distance = HUGEVAL; + return; + } + wpt2 = xte_rec->intermed->next->wpt; + + xte_rec->distance = linedist( + wpt1->latitude, wpt1->longitude, + wpt2->latitude, wpt2->longitude, + wpt3->latitude, wpt3->longitude ); +} + + +int +compare_xte( const void *a, const void *b ) +{ + double foo = (((struct xte *)a)->distance - ((struct xte *)b)->distance ); + if ( foo < 0 ) return 1; + if ( foo > 0 ) return -1; + return 0; +} + +void +routesimple_head( const route_head *rte ) +{ + cur_rte = NULL; + /* build array of XTE/wpt xref records */ + xte_count = 0; + tmpprev = NULL; + + /* short-circuit if we already have fewer than the max points */ + if ( count >= rte->rte_waypt_ct) return; + + xte_recs = xcalloc( rte->rte_waypt_ct, sizeof (struct xte)); + cur_rte = rte; + +} + +void +shuffle_xte( struct xte *xte_rec ) +{ + struct xte tmp_xte; + while ( xte_rec > xte_recs && + xte_rec->distance > xte_rec[-1].distance ) { + tmp_xte.distance = xte_rec->distance; + tmp_xte.ordinal = xte_rec->ordinal; + tmp_xte.intermed = xte_rec->intermed; + xte_rec->distance = xte_rec[-1].distance; + xte_rec->ordinal = xte_rec[-1].ordinal; + xte_rec->intermed = xte_rec[-1].intermed; + xte_rec->intermed->xte_rec = xte_rec; + xte_rec--; + xte_rec->distance = tmp_xte.distance; + xte_rec->ordinal = tmp_xte.ordinal; + xte_rec->intermed = tmp_xte.intermed; + xte_rec->intermed->xte_rec = xte_rec; + } + while ( xte_rec - xte_recs < xte_count-2 && + xte_rec->distance < xte_rec[1].distance ) { + tmp_xte.distance = xte_rec->distance; + tmp_xte.ordinal = xte_rec->ordinal; + tmp_xte.intermed = xte_rec->intermed; + xte_rec->distance = xte_rec[1].distance; + xte_rec->ordinal = xte_rec[1].ordinal; + xte_rec->intermed = xte_rec[1].intermed; + xte_rec->intermed->xte_rec = xte_rec; + xte_rec++; + xte_rec->distance = tmp_xte.distance; + xte_rec->ordinal = tmp_xte.ordinal; + xte_rec->intermed = tmp_xte.intermed; + xte_rec->intermed->xte_rec = xte_rec; + } +} + +void +routesimple_tail( const route_head *rte ) +{ + int i; + if ( !cur_rte ) return; + + /* compute all distances */ + for (i = 0; i < xte_count ; i++ ) { + compute_xte( xte_recs+i ); + } + + + /* sort XTE array, lowest XTE last */ + qsort( xte_recs, xte_count, sizeof( struct xte ), compare_xte ); + + for (i = 0; i < xte_count; i++ ) { + xte_recs[i].intermed->xte_rec = xte_recs+i; + } + /* while we still have too many records... */ + while ( count < xte_count ) { + i = xte_count - 1; + /* remove the record with the lowest XTE */ + route_del_wpt( (route_head *)(void *)rte, + (waypoint *)(void *)(xte_recs[i].intermed->wpt)); + + if ( xte_recs[i].intermed->prev ) { + xte_recs[i].intermed->prev->next = xte_recs[i].intermed->next; + compute_xte(xte_recs[i].intermed->prev->xte_rec); + shuffle_xte(xte_recs[i].intermed->prev->xte_rec); + } + if ( xte_recs[i].intermed->next ) { + xte_recs[i].intermed->next->prev = xte_recs[i].intermed->prev; + compute_xte(xte_recs[i].intermed->next->xte_rec); + shuffle_xte(xte_recs[i].intermed->next->xte_rec); + } + xte_count--; + free_xte( xte_recs+xte_count); + /* end of loop */ + } + if ( xte_count ) { + do { + xte_count--; + free_xte( xte_recs+xte_count ); + } while(xte_count); + } + xfree( xte_recs ); +} + +void +routesimple_process( void ) +{ + route_disp_all( routesimple_head, routesimple_tail, routesimple_waypt_pr ); +} + +void +routesimple_init(const char *args) { + char *fm; + + count = 0; + + if ( global_opts.objective != rtedata && + global_opts.objective != trkdata ) { + fatal(MYNAME ": This filter only works in route (-r) mode."); + } + if (countopt) { + count = atol(countopt); + } + else { + fatal( MYNAME ": You must specify a maximum size for the new route"); + } +} + +void +routesimple_deinit(void) { + /* do nothing */ +} + +filter_vecs_t routesimple_vecs = { + routesimple_init, + routesimple_process, + routesimple_deinit, + routesimple_args +}; diff --git a/testo b/testo index 8741ce67a..34292c02c 100755 --- a/testo +++ b/testo @@ -418,8 +418,14 @@ ${PNAME} -i xmap -f reference/arcdist_input.txt \ -o xmap -F ${TMPDIR}/polygon.txt compare ${TMPDIR}/polygon.txt reference/polygon_output.txt - - +# +# Simplify filter +# +rm -f ${TMPDIR}/simplify.txt +${PNAME} -r -i gpx -f reference/route/route.gpx \ + -x simplify,count=10 \ + -o arc -F ${TMPDIR}/simplify.txt +compare ${TMPDIR}/simplify.txt reference/simplify_output.txt # # This is nasty. If we have a dictionary handy, treat it as a list of -- 2.30.2